'''
Created on Jun 30, 2011

@author: anupams

Works only for unique numbers.
'''

from com.anupam.common.utils import Utils

class MergeSortAnupam(object):

  def __init__(self):
    self.output = None
    self.loopcount = 0
    pass

  def checkIfSortedCorrectly(self,arr):
    size = len(arr)
    size = size -1
    for i in range(0,size ):
      if arr[i] > arr[i + 1]:
        print 'incorrect' + str(i)

  def __copyRemianderElements(self, arr,arrIndex , temp):
    lengthArr = len(arr)
    while arrIndex < lengthArr:
        temp.append(arr[arrIndex])
        arrIndex = arrIndex + 1
        self.loopcount = self.loopcount + 1

  def __merge(self,arr1, arr2):
    len1 = len(arr1)
    len2 = len(arr2)
    i = 0
    j = 0
    k = 0
    temp = []
    while i < len1 and j < len2:
      if arr1[i] < arr2[j]:
        temp.append(arr1[i])
        i = i + 1
      elif arr2[j] < arr1[i]:
        temp.append(arr2[j])
        j = j + 1
      self.loopcount = self.loopcount + 1
      k = k + 1
    if i < len1:
      self.__copyRemianderElements(arr1, i, temp)
    else:
      self.__copyRemianderElements(arr2, j, temp)
    return temp

  def divide(self,arr):
    size = len(arr)
    tempLow = []
    tempHigh = []
    if size > 1:
      tempLow = arr[ :(size/2)]
      tempHigh = arr[size/2 : ]
      tempLow = self.divide(tempLow)
      tempHigh = self.divide(tempHigh)
      result = self.__merge(tempLow, tempHigh)
      self.output = result
      return result
    else:
      return arr


if __name__ == '__main__':
  util = Utils()
  arr = util.generateNumbers(16)
  #print 'pre sorting  ' + str(arr)
  short = MergeSortAnupam()
  short.divide(arr)
  print 'post sorting ' + str(short.output)
  print 'total comparison count ' + str(short.loopcount)